import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class MaxSlidingWindow {
    public static void main(String[] args) {
        int[] test1 = {1,3,-1,-3,5,3,6,7};
        int k1 = 3;
        MaxSlidingWindow maxSlidingWindow = new MaxSlidingWindow();
        System.out.println(Arrays.toString(maxSlidingWindow.maxSlidingWindowByLeftRight(test1,k1)));
    }
    public int[] maxSlidingWindowByBigStack(int[] nums, int k) {
        int[] result = new int[nums.length-k+1];
        PriorityQueue<Integer> integers = new PriorityQueue<>((o1, o2) -> o2-o1);
        for (int i = 0; i < k; i++) {
            integers.add(nums[i]);
        }
        result[0] = integers.peek();
        for (int i = 1; i <= nums.length - k ; i++) {
            integers.remove(nums[i-1]);
            integers.add(nums[i+k-1]);
            result[i] = integers.peek();
        }
        return result;
    }

    public int[] maxSlidingWindowByQueue(int[] nums, int k) {
        int[] result = new int[nums.length -k +1];
        ArrayDeque<Integer> integers = new ArrayDeque<>();
        for (int i = 0; i < k; i++) {
            while(!integers.isEmpty() && nums[integers.getLast()]<nums[i]){
                integers.removeLast();
            }
            integers.addLast(i);
        }
        result[0] = nums[integers.getFirst()];
        for (int i = 1; i <= nums.length - k; i++) {
            if(integers.getFirst() == i-1 ){
                integers.removeFirst();
            }
            while(!integers.isEmpty() && nums[integers.getLast()]<nums[i+k-1]){
                integers.removeLast();
            }
            integers.addLast(i+k-1);
            result[i] = nums[integers.getFirst()];
        }
        return result;
    }

    public int[] maxSlidingWindowByLeftRight(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n -k +1];
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 0; i < n; i++) {
            if( i % k ==0 ){
                left[i] = nums[i];
            }else{
                left[i] = Math.max(nums[i],left[i-1]);
            }
            int j = n-i-1;
            if(j == n-1 || j%k == k-1){
                right[j] = nums[j];
            }else{
                right[j] =Math.max(nums[j],right[j+1]);
            }
        }
        for (int i = 0; i <= n-k; i++) {
            result[i] = Math.max(right[i],left[i+k-1]);
        }
        return result;
    }
}
